package com.mgq.algorithm.link;

import java.util.PriorityQueue;

/**
 * @author MaGuangQi
 * 23题, 合并k个有序链表
 * @date 2021-12-31 10:22
 **/
public class MergeKList_23 {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length==0) return null;
        //首先要找出k的链表中的最小值
        //因为2个链表我们可以直接比较,但是k个就没办法直接比较
        //解决办法: 使用小根堆.
        PriorityQueue<ListNode> queue = new PriorityQueue<>(lists.length,(a,b)-> a.val- b.val);
        //dummy节点
        ListNode dummy = new ListNode(-1);
        ListNode pre=dummy;
        for (ListNode head : lists) {
            if (head != null) {
                //优先队列pq中的元素个数最多是k,每次add 时间复杂度 O(logK),总共N个节点.N(logK)
                queue.add(head);
            }
        }
        while (!queue.isEmpty()) {
            //获取最小的节点
            ListNode node = queue.poll();
            pre.next=node;
            //判断链表是否有下一个. 重点在这....
            //不断的把链表的下一个node加入到小根堆中.小根堆每次弹出的是最小的
            if (node.next != null) {
                queue.add(node.next);
            }
            //pre指针需要移动(重点)
            pre=pre.next;
        }
        return dummy.next;
    }
}


